package year2023.sort;

public class Code07_ShellSort {

    public static void shellSort(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }
        // 步长依次为5、2、1
        // 在插入排序中，一步一步往前交换，直到左边的数<=当前的数，停止
        // 在希尔排序中，如果步长依次为5、2、1
        // 那么来到每个数，每次跳5步往前交换，直到往前5步的数<=当前的数，停止
        // 然后再来到每个数，每次跳3步往前交换，直到往前3步的数<=当前的数，停止
        // 然后再来到每个数，每次跳1步往前交换，直到往前1步的数<=当前的数，停止
        int[] step = { 5, 2, 1 };
        for (int s = 0; s < step.length; s++) {
            for (int i = 0; i < arr.length; i++) {
                for (int j = i - step[s]; j >= 0 && arr[j] > arr[j + step[s]]; j -= step[s]) {
                    swap(arr, j, j + step[s]);
                }
            }
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
}
